package vip.zhenzicheng.algorithm.leetcode.dp;

/**
 * <a href="https://leetcode.cn/problems/jump-game/">跳跃游戏 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-20 11:58
 */
public class JumpGame_55 {

  /*迭代法*/
  // public boolean canJump(int[] nums) {
  //   // 从倒数第二个开始往前找
  //   for (int i = nums.length - 2; i >= 0; i--) {
  //     if (nums[i] == 0) { // 只要找到0说明跳不动，需要往前找一个能跳过去的大小
  //       int skipSize = 1;
  //       while (nums[i] < skipSize) { // 找一个最近的一个能跳过去的元素，退出循环说明满足
  //         i--; // 往前找
  //         skipSize++; // 找一个能跳过去的，每次找不见都需要找一个更大的为了能跳过去
  //         if (i < 0) return false;
  //       }
  //     }
  //   }
  //   return true;
  // }

  /*基于动态规划*/
  public boolean canJump(int[] nums) {
    int maxStep = nums[0]; // 记录每次能跳跃的最大长度
    for (int i = 1; i < nums.length; i++) {
      if (maxStep == 0) return false;
      // 遍历到当前元素时，上一次能跳的最大长度应该减一
      maxStep = Math.max(maxStep - 1, nums[i]);
    }
    return true;
  }
}
